Digital communication and storage of image data is a difficult task due to the sheer volume of digital data required to accurately describe a video sequence. In video, the amount of data quickly becomes very large. Global motion estimation may be used in combination with a block-based motion estimation algorithm to describe image and video data. It may also be used to achieve effects, such as zoom and pan effects. With motion estimation, the amount of data needed to describe, for example, a video sequence may be greatly reduced, as are the demands on storage media and channels, whether internal hardware channels or communication media.
In general, global motion describes the coherent component of motions of different constituent parts of an image or a portion of an image, by a parameterized motion model. The process of estimating these parameters is known as Global Motion Estimation. A global motion may arise due to actual changing of image components, and also arises due to the apparent motion of image background, which can be induced by a camera change, such as pan, zoom, or a camera view from a different point of origin (e.g., a second camera angle viewing the same image). All of these and other changes can induce global motion.
Global motion estimation may therefore be used (by itself or in combination with a block-based motion estimation algorithm) to accomplish video compression, segmentation, mosaicing, format conversion, image registration, camera stabilization and other similar image handling tasks and image manipulation effects. In the art, global motion estimation methods can be broadly classified into two categories by the operational domains. A first class are those that operate in the spatial domain. A second class are those that operate in the frequency domain.
Most common spatial domain methods include those based on minimization of SSD (sum of squared difference) or SAD (sum of absolute difference) error metric. SSD minimization is typically accomplished by gradient descent methods like ML (Marquardt-Levenburg). Such techniques are iterative. Each iteration involves image warping and re-computation of derivatives. Accordingly, the techniques are inherently computationally intensive and slow.
Several speed-up strategies have been proposed. One strategy is the use of a multi-resolution framework. See, e.g. R. Szeliski and J. Coughlan, “Hierarchical Spline-Based Image Registration,” Proceedings CVPR-1994 (IEEE Computer Society conference on Computer Vision and Pattern Recognition), Vol. 1, pp. 194-201 (June 1994). Another strategy is a modification of the Marquardt-Levenberg (ML) method. See, e.g., A. Averbuch and Y. Keller, “Fast Motion Estimation Using Bi-Directional Gradient Methods,” Proceedings ICASSP-2002 (IEEE International Conference on Acoustics, Speech and Signal Processing), Vol. 4, pp. 3616-3619, (May 2002). Selective integration and warp free formulation have also been proposed. See, e.g., Y. Keller and A. Averbuch, “Fast Gradient Methods Based on Global Motion Estimation for Video Compression,” IEEE Transactions on Circuits and Systems for Video Technology, 13(4):300-309 (April 2003).
The SAD error metric is easier to compute compared to SSD, and its minimization is typically accomplished by a direct search of parameter space. However, the complexity of search increases exponentially with number of parameters. SSD and SAD minimization based techniques suffer from the disadvantage that they might get stuck in local minima, although it is less likely in multi resolution framework.
To deal with large motion, log-polar domain coarse estimation followed by refinement using ML optimization has also been proposed (See, G. Wolberg and S. Zokai, “Robust Image Registration Using Log-Polar Transform,” Proceedings ICIP-2000 (IEEE International Conference on Image Processing), Vol. 1, pp. 493-496 (September 2000)) but due to log-polar mapping in spatial domain, this method is not suitable when there is a foreground object at the center of coordinate system.
Feature based methods rely on extraction and tracking of feature points. A motion parameter is obtained by robust least square fitting to the coordinates of feature points. Extracting reliable features and discarding unreliable ones such as those belonging to foreground and occlusion junctions, and handling of newly appearing and disappearing features are very difficult problems, however. A closely related class of methods uses motion vectors of blocks instead of the coordinates of feature points, which is very suitable for MPEG-2 to MPEG-4 transcoding since motion vectors are already computed. The range and accuracy of these methods is limited by range and accuracy of motion vectors. Additionally, if a motion vector is not available, the computational cost of finding them for a reasonable range of motion vectors and sub-pixel accuracy can be prohibitive.
Among frequency domain techniques, phase correlation is a very popular and efficient technique for motion estimation. In its original form, it can only handle integer-pixel translations. By adopting interpolation of the correlation surface and polyphase decomposition of the cross power spectrum, it has been extended to sub-pixel translations. Re-sampling the Fourier magnitude spectra on a log-polar grid has been introduced to also estimate scaling and rotation using phase-correlation, and it has been used in image registration and global motion estimation.
Estimation of the affine parameters in the frequency domain is based upon the Affine Theorem of Fourier Transform. See, R. N. Bracewellet al., “Affine Theorem for Two-Dimensional Fourier Transform,” Electronics Letters, 29(3):304 (February 1993). In this approach, the Fourier shift property is exploited to achieve translation invariance by taking the magnitude of the Fourier spectra of images. By working in this translation invariant domain, known as the Fourier-Mellin domain, a linear matrix component (A) of affine transformation can be determined independent of a translational vector component (B). Once the linear component has been determined, it can be compensated for and translation can be determined using Phase-correlation.
Parametric models that have been used to achieve global motion estimation include the 2-parameter translation model, 4-parameter rotation-scale-translation (RST) model, 6-parameter affine model, and the 8-parameter projective model. The affine motion model is widely used because it provides an acceptable tradeoff between generality and ease of estimation. The primary difficulties in applying the affine motion model include the possibility of large motions, differently moving foreground objects, and appearing and disappearing image regions. Accounting for these problems tends to make application of the affine model complex, while the failure to account for these problems can lead to poor estimations in certain instances, and a resultant poor image.